#include <string>
#include <set>
#include <vector>
#include <array>
#include <climits>
#include <iostream>

struct Range
{
	size_t begin;
	size_t end;
};

bool operator < (const Range& r1, const Range& r2)
{
	return (r1.begin < r2.begin) || (r1.begin == r2.begin && r1.end < r2.end);
}

class Solution
{
public:
	bool isScramble(std::string s1, std::string s2)
	{
		auto length = s1.length();
		std::vector<std::vector<std::set<Range>>> dp(length, std::vector<std::set<Range>>(length));
		std::array<std::set<size_t>, 256> alphaSet;
		std::cout << "alphaSet" << std::endl;
		for (size_t i = 0; i < length; i++)
			alphaSet[s2[i]].insert(i);
		std::cout << "stride = 1" << std::endl;
		for (size_t i = 0; i < length; i++) {
			for (auto index : alphaSet[s1[i]]) {
				dp[i][i].insert(Range{ index, index });
			}
		}
		std::cout << "stride = 2" << std::endl;
		for (size_t i = 0; i < length - 1; i++) {
			for (size_t j = 0; j < length - 1; j++) {
				if ((s1[i] == s2[j] && s1[i + 1] == s2[j + 1]) || (s1[i + 1] == s2[j] && s1[i] == s2[j + 1])) {
					dp[i][i + 1].insert(Range{ j, j + 1 });
				}
			}
		}
		std::cout << "loop begin" << std::endl;
		for (size_t stride = 2; stride < length; stride++) {
			for (size_t begin = 0; begin < length - stride; begin++) {
				auto end = begin + stride;
				for (size_t firstEnd = begin; firstEnd < end; firstEnd++) {
					for (auto& first : dp[begin][firstEnd]) {
						for (auto& second : dp[firstEnd + 1][end]) {
							if (first.end + 1 == second.begin)
								dp[begin][end].insert(Range{ first.begin, second.end });
							if (second.end + 1 == first.begin)
								dp[begin][end].insert(Range{ second.begin, first.end });
						}
					}
				}
			}
		}
		return !dp[0][length - 1].empty();
	}
};

int main()
{
	Solution s;
	std::cout << std::boolalpha << s.isScramble("great", "rgtae") << std::endl;
	system("pause");
	return 0;
}